/**
 * 
 * @author max
 * Heap that primarily uses the book's code (and its online references/source code)
 * to implement the heap. We use a maxheap to simply grab the largest memory block
 * available, insert our data, and then update our "free" blocks to represent the allocation. In
 * the event the largest available block of memory isn't large enough, we defrag by combining
 * continuous blocks of unallocated memory, and attempt to allocate the block again, once again
 * in the largest block available.
 */

public class Heap implements MemoryManager{

	private static int ID = 1;

	public Memory[] usedMemory;
	public SortingArray array;
	public HeapGeneric<Memory> heap;

	/**
	 *  Constructor that takes a max memory size. Generates an array of size 5 (arbitrary)
	 *  which gives the heap 4 usable blocks. We then allocate a block of free memory.
	 *  @param MemSize the total amount of memory alloted to the Heap.
	 */     public Heap(int MemSize){
		 array = new SortingArray();
		 usedMemory = new Memory[4];
		 heap = new HeapGeneric<Memory>(4);
		 heap.insert(new Memory(MemSize)); //Free memory, one Memory "block" of max size
		 array.insert(heap.findMax());
	 }

	 /**
	  * Method for allocating memory. Creates a new memory block of size
	  * "size" and assigns it a unique UID. Then it attempts to allocate the memory into the heap.
	  * If it fails, it will return the appropriate String that will tell the main driver program to
	  * attempt a defrag and try the allocation again.
	  * @param size Size of a new memory block to allocate
	  * @return String ID and address of the new Memory, if address = -1, run defrag
	  */
	 public String allocate(int size) {
		 Memory find = heap.findMax();
		 Memory m = null;
		 if(find!=null)
			 if (find.size() >= size) m = find; //If the largest block can fit the requested allocation, otherwise m = null.

		 while (ID >= usedMemory.length) { //if full, double the size...
			 Memory[] temp = new Memory[usedMemory.length * 2];
			 for (int i = 0; i < usedMemory.length; i++)
				 temp[i] = usedMemory[i];
			 usedMemory = temp;
		 }

		 if (m == null) //Failed allocation.
			 return ID++ + " " + -1;
		 

		 usedMemory[ID] = new Memory(size, m.address(), ID);
		 array.remove(m.address());
		 heap.deleteMax();
		 
		 m.setSize(m.size() - size);
		 m.setAddress(m.address()+size);

		 if(m.size()!=0){ //Don't want any blocks of zero memory, hence the removals above.
		 heap.insert(m);
		 array.insert(m);
		 };
		 return ID + " " + usedMemory[ID++].address();
	 }       

	 /**
	  * Deallocate memory given a UID. 
	  * @param UID UID of the memory to free up
	  * @return String success or failure as a String, makes it easier to create output.
	  */
	 public String deallocate(int UID) {
		 if(UID < 0 || UID >= usedMemory.length)
			 return "FAILED";
		 
		 Memory m = usedMemory[UID];

		 if(m==null) //In the event the allocation failed or hasn't yet reach this number of allocations, deallocation fails.
			 return "FAILED";


		 array.insert(m);
		 //m.setId(-1);
		 heap.insert(m);
		 usedMemory[UID] = null;
		 return "SUCCESS";
	 }

	 /**
	  *  Defragging is done primarily in a separate array, where it's easy to
	  *  tell whether blocks of free memory are contiguous or not. If they are, combine them
	  *  and then shove them back into the heap.
	  */
	 public void defrag() {
		 array = array.defrag();
		 heap.makeEmpty();
		 ID--;

		 for(Memory m : array){
			 if(m!=null)
				 heap.insert(m);
		 }
	 }

	 /**
	  * @return int  of currently allocated blocks of memory.
	  */
	 public int getSize() {
		 return heap.getSize();
	 }

	 /**
	  * @return boolean Whether or not the heap is empty.
	  */
	 public boolean isEmpty() {
		 return getSize()==0;
	 }

	 /**
	  * Sort and give the time to Statistics for it to keep track of.
	  * @param s Statistics class that keeps track of the time it takes to perform certain operations.
	  */
	 public void sort(Statistics s) throws InterruptedException
	 {
		 array.quicksort(s);
		 array.bucketsort(s);
	 }

	 /**
	  * toString method, returns heap and its array of allocated memory.
	  */
	 public String toString(){
		 return heap.toString();
	 }
}